//现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。 
//
// 
//
// 示例 1： 
//
// 
//输入: bamboo_len = 12
//输出: 81
// 
//
//提示：
//
// 
// 2 <= bamboo_len <= 58 
// 
//
// 注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/ 
//
// Related Topics 数学 动态规划 👍 631 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-04-28 09:47:06
 * @description LCR 131.砍竹子 I
 
 */
 
public class JianShengZiLcof {
    public static void main(String[] args) {
    //测试代码
    JianShengZiLcof fun = new JianShengZiLcof();
    Solution solution= fun.new Solution();
    solution.cuttingBamboo(8);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //1.怎么判断一个数要不要再分
    //只要分出的结果不含1，那么结果一定会变大
    //(a+b)=c,  a*b>c
    //ab−a−b>0  ，ab−a−b+1>1，ab−a−b+1=a(b−1)−(b−1)=(a−1)(b−1)
    //(a−1)(b−1)>1
    //即a,b都大于1时，  a*b>c
    //2.已经有一个数，怎么分最大
    //假设我们将竹子分成 k 段，每段长度为 x，那么 x = n / k（假设均匀分割），乘积为 x^k = (n/k)^k。
        //
        //为了最大化 (n/k)^k，可以对它取自然对数（因为对数函数是单调递增的，最大化对数等价于最大化原函数）：
        //
        //ln(P) = k * ln(n/k) = k * (ln(n) - ln(k))
        //
        //对 k 求导并令导数为0：
        //
        //d/dk [k * (ln(n) - ln(k))] = ln(n) - ln(k) - 1 = 0
        //
        //ln(n/k) = 1
        //
        //n/k = e
        //
        //k = n/e
        //
        //因此，最优的每段长度 x ≈ e ≈ 2.718。由于长度必须是整数，我们选择最接近 e 的整数，即3。
            //当 n 除以3余1时，因为 3 + 1 = 4，而 2 × 2 > 3 × 1，所以应该将一个3和1替换为两个2。
        //
        //类似地，如果余2，则保留一个2。
    public int cuttingBamboo1(int bamboo_len) {
        if(bamboo_len<3) return 1;
        if(bamboo_len==3) return 2;
        int res=1;
        while (bamboo_len>4){
            res*=3;
            bamboo_len-=3;
        }
        res*=bamboo_len;
        return res;
    }
    /*
    *
    * 对于每个长度 i 从2到 bamboo_len，
    * 尝试所有可能的分割点 j（从1到 i-1），计算两种情况的乘积：
        不进一步分割 j：j * (i - j)
        进一步分割 j：j * dp[i - j]
        取这两种情况的最大值来更新 dp[i]。
    * */
    public int cuttingBamboo2(int bamboo_len) {
        int[] dp = new int[bamboo_len + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= bamboo_len; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[bamboo_len];
    }
    //每个位置的最大值，其实都是当前-2或者-3得来的
    //每个位置可以贡献的值为，不切割，或者切割两者的最大值，比如3，切割的贡献是2，不切割贡献是3
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int[] dp = new int[bamboo_len + 1];
        dp[2] = 1;
        for (int i = 3; i <= bamboo_len; i++) {
            dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[bamboo_len];
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
